package com.dai.code;

import java.util.Arrays;

/**
 * 切木头
 * @author daijiyong
 */
public class CutWood {

    public static void main(String[] args) {
        int[] woods = {100, 110, 50, 60, 100, 90};
        int specifyLen = 30;
        int specifyNum = 9;
        System.out.println(Arrays.toString(woods));
        System.out.printf("给定一组木头，要求切成%d长度，最多能切成%d根%n", specifyLen, cutWoods2SpecifyLen(woods, specifyLen));
        System.out.printf("给定一组木头，要求切成等长的%d根，能得到的最长长度为%d%n", specifyNum, cutWoods2SpecifyNum(woods, specifyNum));
    }

    public static Integer cutWoods2SpecifyLen(int[] woods, int len) {
        if (woods == null || woods.length == 0) {
            return 0;
        }
        int result = 0;
        for (int wood : woods) {
            result += wood / len;
        }
        return result;
    }

    public static Integer cutWoods2SpecifyNum(int[] woods, int num) {
        if (woods == null || woods.length == 0) {
            return 0;
        }
        int result = 0;
        int min = 1;
        int max = getMaxLen(woods);
        while (min + 1 < max) {
            result = (min + max) / 2;
            // 计算在给定长度result的情况，能够切出几根
            int numTemp = cutWoods2SpecifyLen(woods, result);
            if (numTemp >= num) {
                min = result;
            } else {
                max = result;
            }
        }
        if (cutWoods2SpecifyLen(woods, max) >= num) {
            return max;
        }
        if (cutWoods2SpecifyLen(woods, min) >= num) {
            return min;
        }

        return result;
    }

    private static int getMaxLen(int[] woods) {
        int result = woods[0];
        for (int i = 1; i < woods.length; i++) {
            if (woods[i] > result) {
                result = woods[i];
            }
        }
        return result;
    }
}
